class Heap {
  /**
   * constructor
   * @param {function} compare(a,b)
   */
  constructor (compare) {
    this._compare = compare
    this._data = []
  }

  push (element) {
    this._data.push(element)
    let index = this._data.length - 1
    // 比父节点大，往上走
    while (index > 0 && this._compare(this._data[index], this._data[this._parentIndex(index)])) {
      this._swap(index, this._parentIndex(index))
      index = this._parentIndex(index)
    }
  }

  _parentIndex (index) {
    return index === 0 ? index : Math.floor((index - 1) / 2)
  }

  size () {
    return this._data.length
  }

  _swap (i, j) {
    const temp = this._data[i]
    this._data[i] = this._data[j]
    this._data[j] = temp
  }

  pop () {
    this._swap(0, this._data.length - 1)
    const result = this._data.pop()
    let index = 0
    let left = 2 * index + 1
    while (left < this._data.length) {
      const right = left + 1 < this._data.length ? left + 1 : left
      // left比right大
      const swapIndex = this._compare(this._data[left], this._data[right]) ? left : right
      // cur index > child
      if (this._compare(this._data[index], this._data[swapIndex])) {
        break
      }
      this._swap(index, swapIndex)
      index = swapIndex
      left = 2 * index + 1
    }
    return result
  }

  peek () {
    return this._data[0]
  }
}

export default Heap
